package queen;

import java.util.LinkedList;
import java.util.Queue;

public class 岛屿数量 {
    public static void main(String[] args) {

    }

    class Solution {
        public int BFSnumIslands(char[][] grid) {
            //二维数组为空，岛屿数量为0
            if (grid == null || grid.length == 0) {
                return 0;
            }

            int nrow = grid.length; //二维数组的行数
            int ncol = grid[0].length;  //二维数组列数
            int numIslands = 0;   //初始化岛屿数量为0

            //遍历二维数组
            for (int row = 0; row < nrow; ++row) {
                for (int col = 0; col < ncol; ++col) {
                    if (grid[row][col] == '1') {   //扫描到第一个‘1’的点，则代表搜索开始
                        ++numIslands;           //说明找到一个岛屿
                        grid[row][col] = '0';     //将其置为0
                        Queue<Integer> neighbors = new LinkedList<>();  //用于存储该点附近的点
                        neighbors.add(row * ncol + col);    //表示二维数组从上到下从左到右数，即该点在数组的位置
                        while (!neighbors.isEmpty()) {    //如果数组不为空则取出队首元素进行对四周查找
                            int id = neighbors.remove();    //获取位置
                            int therow = id / ncol;
                            int thecol = id % ncol;       //通过 row*ncol+col 这一信息得出当前取出点在二维数组的位置

                            //该点的上方邻点
                            if (therow - 1 >= 0 && grid[therow - 1][thecol] == '1') {
                                neighbors.add((therow - 1) * ncol + thecol);
                                grid[therow - 1][thecol] = '0';
                            }
                            //该点的下方邻点
                            if (therow + 1 < nrow && grid[therow + 1][thecol] == '1') {
                                neighbors.add((therow + 1) * ncol + thecol);
                                grid[therow + 1][thecol] = '0';
                            }

                            //该点的左邻点
                            if (thecol - 1 >= 0 && grid[therow][thecol - 1] == '1') {
                                neighbors.add(therow * ncol + thecol - 1);
                                grid[therow][thecol - 1] = '0';
                            }

                            //该点的右邻点
                            if (thecol + 1 < ncol && grid[therow][thecol + 1] == '1') {
                                neighbors.add(therow * ncol + thecol + 1);
                                grid[therow][thecol + 1] = '0';
                            }
                        }

                    }

                }
            }
            return numIslands;
        }

        public int DFSnumIslands(char[][] grid) {
            int count = 0;  //初始化岛屿数量
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    if (grid[i][j] == '1'){
                        dfs(grid,i,j);
                        count++;
                    }
                }
            }

            return count++;
        }

        private void dfs(char[][] grid, int i, int j) {
            //防止越界和重复遍历
            if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == 0){
                return;
            }
            grid[i][j] = '0';
            dfs(grid,i+1,j);
            dfs(grid,i,j+1);
            dfs(grid,i-1,j);
            dfs(grid,i,j-1);

        }
    }
}
